#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
using namespace std;
//
//int main()
//{
//    int n = 0, m = 0, q = 0;
//    cin >> n >> m >> q;
//
//    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> arr[i][j];
//
//    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
//
//    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
//
//    while (q--)
//    {
//        cin >> x1 >> y1 >> x2 >> y2;
//        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
//    }
//
//    return 0;
//}

//class Solution
//{
//public:
//    int pivotIndex(vector<int>& nums)
//    {
//        int n = nums.size();
//        vector<int> f(n), g(n);
//
//        for (int i = 1; i < n; i++)
//            f[i] = f[i - 1] + nums[i - 1];
//        for (int i = n - 2; i >= 0; i--)
//            g[i] = g[i + 1] + nums[i + 1];
//
//        for (int i = 0; i < n; i++)
//            if (f[i] == g[i])
//                return i;
//        return -1;
//    }
//};

class Solution
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);

        f[0] = g[n - 1] = 1;
        for (int i = 1; i < n; i++)
            f[i] = f[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];

        vector<int> ret(n);
        for (int i = 0; i < n; i++)
            ret[i] = f[i] * g[i];
        return ret;
    }
};